BZOJ3994【SDOI2015】约数个数和 <莫比乌斯反演>

Problem

【SDOI2015】约数个数和

Description

设为的约数个数，给定，求

Input

输入文件包含多组测试数据。
第一行，一个整数，表示测试数据的组数。
接下来的行，每行两个整数。

Output

行，每行一个整数，表示你所求的答案。

Sample Input

1
2
3

2
7 4
5 6

Sample Output

1
2

110
121

HINT

标签：莫比乌斯反演

Solution

挺神的反演，没推出来，需要一个结论。

首先考虑如何把变为我们更为熟悉的数学语言。
对于，考虑的约数，每个约数均可表示为，其中。那么用统计约数，一定会不漏地枚举到所有约数，但显然是有重复的。注意到这种重复的造成只有一种情况，即若符合条件，那么也符合条件，而两者所代表的最终约数是相同的，重复计数。也就是说只要，那么一定是重复计算的。于是不重不漏地计算只需要把中的加上的限制即可。
因此推出重要结论。

接下来就可以推反演了：

如果能预处理出的值，就可以根号分块计算答案。

考虑的意义，即枚举一个数，统计其在内的倍数有多少个，可以理解为枚举约数，计算它在中是多少个数的约数，即计算其对的贡献。于是，我们需要预处理出。

由于是积性函数，对于，我们有：

：
：，其中一定为的最小质因子

为了应对情况，我们需要预处理最小质因子次数，注意到也可以线性筛预处理：

对于质数，
对于正整数和质数，
- ：
- ：

如此我们即可线性筛预处理出，计算前缀和，对于询问进行数论分块统计答案，时间复杂度。

Code

#include <bits/stdc++.h>
#define MAX_N 50000
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
bool NotPri[MAX_N+5]; int pri[MAX_N+5], cnt;
lnt mu[MAX_N+5], c[MAX_N+5], d[MAX_N+5], ans;
void init() {
    mu[1] = 1, d[1] = 1;
    for (int i = 2; i <= MAX_N; i++) {
        if (!NotPri[i]) pri[cnt++] = i, mu[i] = -1, c[i] = 1, d[i] = 2;
        for (int j = 0; j < cnt; j++) {
            if (i*pri[j] > MAX_N) break;	NotPri[i*pri[j]] = true;
            if (i%pri[j]) mu[i*pri[j]] = -mu[i], c[i*pri[j]] = 1, d[i*pri[j]] = d[i]*d[pri[j]];
            else mu[i*pri[j]] = 0, c[i*pri[j]] = c[i]+1, d[i*pri[j]] = d[i]*(c[i]+2)/(c[i]+1);
            if (i%pri[j] == 0) break;
        }
    }
    for (int i = 2; i <= MAX_N; i++) mu[i] += mu[i-1], d[i] += d[i-1];
}
int main() {
    int n, m, T; read(T), init();
    while (T--) {
        read(n), read(m), ans = 0;
        for (int l = 1, r; l <= min(n, m); l = r+1)
            r = min(n/(n/l), m/(m/l)), 
            ans += (mu[r]-mu[l-1])*d[n/l]*d[m/l];
        printf("%lld\n", ans);
    }
    return 0;
}